//#pragma once
//
//template<class K,class V>
//struct AVLTreeNode
//{
//	pair<K, V> _kv;//键值对
//	AVLTreeNode<K, V>* _left;
//	AVLTreeNode<K, V>* _right;
//	AVLTreeNode<K, V>* _parent;
//
//	int _bf;//balance factor
//
//	AVLTreeNode(const pair<K, V>& kv)
//		:_kv(kv)
//		, _left(nullptr)
//		, _right(nullptr)
//		, _parent(nullptr)
//		,_bf(0)
//	{}
//};
//
//template<class K,class V>
//class AVLTree
//{
//	typedef AVLTreeNode<K, V> Node;
//public:
//	bool Insert(const pair<K, V>& kv)
//	{
//		//一开始是一棵空树
//		if (_root == nullptr)
//		{
//			_root = new Node(kv);
//			return true;
//		}
//		//一开始不是空树
//		Node* parent = nullptr;
//		Node* cur = _root;
//
//		//寻找插入的地方，是左子树还是右子树
//		while (cur)
//		{
//			if (cur->_kv.first < kv.first)
//			{
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (cur->_kv.first > kv.first)
//			{
//				parent = cur;
//				cur = cur->_left;
//			}
//			else
//			{
//				return false;
//			}
//		}
//
//		//找到插入的位置后，即确认了是在左子树还是右子树
//		cur = new Node(kv);
//		//确定是在父节点的左还是右
//		if (parent->_kv.first < kv.first)
//		{
//			parent->_right = cur;
//			cur->_parent = parent;
//		}
//		else
//		{
//			parent->_left = cur;
//			cur->_parent = parent;
//		}
//
//		//更新平衡因子，判断插入后的树，是否是一棵AVL树
//		while (parent)
//		{
//			//插入的是在父节点的左边，即是左孩子
//			if (cur == parent->_left)
//			{
//				parent->_bf--;//一般是右-左，因此，如果是插入在左边，那就是减一
//			}
//			else  //是右孩子
//			{
//				parent->_bf++;
//			}
//
//			//更新完平衡因子后，判断是否是一棵AVL树
//			//如果平衡因子是0，任何节点的平衡因子都没被改变
//			if (parent->_bf == 0)
//			{
//				break;
//			}
//			else if (parent->_bf == 1 || parent->_bf == -1)
//			{
//				//如果平衡因子是1或-1，那么就说明，父节点往上的节点的平衡因子有可能被改变了
//				cur = parent;
//				parent = parent->_parent;
//			}
//			else if (parent->_bf == 2 || parent->_bf == -2)
//			{
//				//旋转
//				//左单旋----高出来的那一部分按下去！
//				if (parent->_bf == 2 && cur->_bf == 1)
//				{
//					RotateL(parent);
//				}
//				else if (parent->_bf == -2 && cur->_bf == -1)//右单旋
//				{
//					RotateR(parent);
//				}
//				else if (parent->_bf == -2 && cur->_bf == 1) //先左单旋，再右单旋
//				{
//					RotateLR(parent);
//				}
//				else if (parent->_bf == 2 && cur->_bf == -1)//先右单旋，再左单旋
//				{
//					RotateRL(parent);
//				}
//				else
//				{
//					assert(false);
//				}
//				break;
//			}
//			else  //不排除在创建一棵AVL树的时候，代码写错了
//			{
//				assert(false);
//			}
//		}
//		return true;
//	}
//	void RotateL(Node* parent)
//	{
//		Node* subR = parent->_right;
//		Node* subRL = subR->_left;
//		//修改子树
//		parent->_right = subRL;
//		if (subRL)
//			subRL->_parent = parent;
//		Node* ppNode = parent->_parent;
//		subR->_left = parent;
//		parent->_parent = subR;
//		//修改根
//		if (ppNode == nullptr)
//		{
//			_root = subR;
//			_root->_parent = nullptr;
//		}
//		else
//		{
//			if (ppNode->_left = parent)
//			{
//				ppNode->_left = subR;
//			}
//			else
//			{
//				ppNode->_right = subR;
//			}
//			subR->_parent = ppNode;
//		}
//		parent->_bf = subR->_bf = 0;
//	}
//	void RotateR(Node* parent)
//	{
//		Node* subL = parent->_left;
//		Node* subLR = subL->_right;
//		//修改子树
//		parent->_left = subLR;
//		if (subLR)
//			subLR->_parent = parent;
//		Node* ppNode = parent->_parent;
//		subL->_right = parent;
//		parent->_parent = subL;
//		//修改根
//		if (ppNode==nullptr)
//		{
//			_root = subL;
//			_root->_parent = nullptr;
//		}
//		else
//		{
//			if (ppNode->_left = parent)
//			{
//				ppNode->_left = subL;
//			}
//			else
//			{
//				ppNode->_right = subL;
//			}
//			subL->_parent = ppNode;
//		}
//		parent->_bf = subL->_bf = 0;
//
//	}
//
//	void RotateLR(Node* parent)
//	{
//		Node* subL = parent->_left;
//		Node* subLR = subL->_right;
//		int bf = subLR->_bf;
//
//		RotateL(parent->_left);
//		RotateR(parent);
//
//		//需要对旋转后的AVL树中，参与旋转的节点的平衡因子进行改写
//		if (bf == -1) //插入在subLR的右子树
//		{
//			parent->_bf = 1;
//			subL->_bf = 0;
//			subLR->_bf = 0;
//		}
//		else if (bf == 1)  //插在subLR的左子树
//		{
//			parent->_bf = 0;
//			subL->_bf = -1;
//			subLR->_bf = 0;
//		}
//		else if (bf == 0) //subLR自己就是新增的节点
//		{
//			parent->_bf = 0;
//			subL->_bf = 0;
//			subLR->_bf = 0;
//		}
//		else
//		{
//			assert(false);
//		}
//	}
//
//	void RotateRL(Node* parent)
//	{
//		//Node* subR = parent->_right;
//		//Node* subRL = subR->_left;
//		//int bf = subRL->_bf;
//
//		//RotateR(parent->_right);
//		//RotateL(parent);
//
//		////需要对旋转后的AVL树中，参与旋转的节点的平衡因子进行改写
//		//if (bf == 1) //插入在subLR的右子树
//		//{
//		//	parent->_bf = 0;
//		//	subR->_bf = -1;
//		//	subRL->_bf = 0;
//		//}
//		//else if (bf == -1)  //插在subLR的左子树
//		//{
//		//	parent->_bf = 1;
//		//	subR->_bf = 0;
//		//	subRL->_bf = 0;
//		//}
//		//else if (bf == 0) //subLR自己就是新增的节点
//		//{
//		//	parent->_bf = 0;
//		//	subR->_bf = 0;
//		//	subRL->_bf = 0;
//		//}
//		//else
//		//{
//		//	assert(false);
//		//}
//	}
//
//	void Inorder()
//	{
//		_Inorder(_root);
//	}
//
//	void _Inorder(Node* root)
//	{
//		if (root == nullptr)
//			return;
//		_Inorder(root->_left);
//		cout << root->_kv.first << ":" << root->_kv.second << endl;
//		_Inorder(root->_right);
//	}
//
//	int Height(Node* root)
//	{
//		if (root == nullptr)
//			return 0;
//
//		int lh = Height(root->_left);
//		int rh = Height(root->_right);
//
//		return lh > rh ? lh + 1 : rh + 1;
//	}
//
//	bool IsBalance()
//	{
//		return _IsBalance(_root);
//	}
//
//	bool _IsBalance(Node* root)
//	{
//		if (root == nullptr)
//			return true;
//
//		//获取左子树的高度
//		int leftHeight = Height(root->_left);
//		//获取右子树的高度
//		int rightHeight = Height(root->_right);
//
//		if (rightHeight - leftHeight != root->_bf)
//		{
//			cout << root->_kv.first << "平衡因子异常" << endl;
//			return false;
//		}
//
//		return abs(rightHeight - leftHeight) < 2
//			&& _IsBalance(root->_left)
//			&& _IsBalance(root->_right);
//
//
//	}
//
//
//
//private:
//	Node* _root = nullptr;
//};



#pragma once
#include<assert.h>
	template<class K, class V>
	struct AVLTreeNode
	{
		pair<K, V> _kv;//键值对
		AVLTreeNode<K, V>* _left;
		AVLTreeNode<K, V>* _right;
		AVLTreeNode<K, V>* _parent;

		int _bf;//balance factor

		AVLTreeNode(const pair<K, V>& kv)
			:_kv(kv)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _bf(0)
		{}
	};

	template<class K, class V>
	class AVLTree
	{
		typedef AVLTreeNode<K, V> Node;
	public:
		bool Insert(const pair<K, V>& kv)
		{
			//一开始是一棵空树
			if (_root == nullptr)
			{
				_root = new Node(kv);
				return true;
			}
			//一开始不是空树
			Node* parent = nullptr;
			Node* cur = _root;

			//寻找插入的地方，是左子树还是右子树
			while (cur)
			{
				if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			//找到插入的位置后，即确认了是在左子树还是右子树
			cur = new Node(kv);
			//确定是在父节点的左还是右
			if (parent->_kv.first < kv.first)
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_left = cur;
				cur->_parent = parent;
			}

			//更新平衡因子，判断插入后的树，是否是一棵AVL树
			while (parent)
			{
				//插入的是在父节点的左边，即是左孩子
				if (cur == parent->_left)
				{
					parent->_bf--;//一般是右-左，因此，如果是插入在左边，那就是减一
				}
				else  //是右孩子
				{
					parent->_bf++;
				}

				//更新完平衡因子后，判断是否是一棵AVL树
				//如果平衡因子是0，任何节点的平衡因子都没被改变
				if (parent->_bf == 0)
				{
					break;
				}
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					//如果平衡因子是1或-1，那么就说明，父节点往上的节点的平衡因子有可能被改变了
					cur = parent;
					parent = parent->_parent;
				}
				else if (parent->_bf == 2 || parent->_bf == -2)
				{
					//旋转
					//右单旋----高出来的那一部分按下去！
					if (parent->_bf == -2 && cur->_bf == -1)
					{
						RotateR(parent);
					}
					else  if (parent->_bf == 2 && cur->_bf == 1)//左单旋
					{
						RotateL(parent);
					}
					else if (parent->_bf == -2 && cur->_bf == 1) //先左旋后右旋
					{
						RotateLR(parent);
					}
					else if (parent->_bf == 2 && cur->_bf == -1) //先右旋再左旋
					{
						RotateRL(parent);
					}
					else
					{
						assert(false);
					}
					break;

				}
				else  //不排除在创建一棵AVL树的时候，代码写错了
				{
					assert(false);
				}
			}
			return true;
		}

		void RotateR(Node* parent)
		{
			//一开始，例子中的60节点便是parent
			//先创建指向30节点的指针和指向b节点的指针
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			//这一步是让60节点的左孩子指向b节点
			parent->_left = subLR;
			//这一步判断b节点是否为空,如果不为空，那么就让它的双亲节点指向60节点（本来是指向subL的）
			if (subLR)
			{
				subLR->_parent = parent;
			}
			//上面两步成功将b节点改链接到60节点上去
			//先保存60节点的双亲节点
			Node* ppNode = parent->_parent;
			//让30节点subL的右孩子指向60节点，即60节点链接到了30节点subL的右孩子上
			subL->_right = parent;
			//60节点的双亲节点指向30节点subL
			parent->_parent = subL;
			//判断60节点原本的双亲节点是否为空
			//为空
			if (ppNode == nullptr)
			{
				_root = subL;
				_root->_parent = nullptr;
			}
			else  //不为空，说明是一棵子树
			{
				if (ppNode->_left == parent) //如果parent是原先的双亲节点的左孩子
				{
					ppNode->_left = subL;

				}
				else                         //如果parent是原先的双亲节点的右孩子
				{
					ppNode->_right = subL;
				}

				//链接后，再让成为新根后的30节点subL的双亲节点指向ppNode
				subL->_parent = ppNode;
			}

			//最后将30节点subL和60节点parent的平衡因子修改
			//
			subL->_bf = parent->_bf = 0;
			//此时，右单旋完成
			//因为旋转的要求是让这颗子树的高度跟插入前保持一致
			//那就说明，此时完成旋转的这树，不会对上层的平衡因子造成影响，此时就可以结束对这棵树的更新旋转
		}

		void RotateL(Node* parent)
		{
			//创建60节点subR，右右是左旋嘛
			Node* subR = parent->_right;
			//创建指向b节点的指针subRL
			Node* subRL = subR->_left;
			//先让parent的右孩子节点指向subRL。
			parent->_right = subRL;
			//判断subRL是否为空，不为空，那就让subRL的父节点指向parent
			if (subRL)
			{
				subRL->_parent = parent;
			}
			//上面步骤成功将b节点链接到了parent上

			//先把parent的父节点保存起来，不管存在不存在
			Node* ppNode = parent->_parent;
			//接下来就是把parent按下了，成为subR的左孩子，让subR成为新根
			subR->_left = parent;
			parent->_parent = subR;
			//让subR成为新根
			if (ppNode == nullptr)
			{
				_root = subR;
				_root->_parent = nullptr;
			}
			else
			{
				if (ppNode->_left == parent)
				{
					ppNode->_left = subR;
				}
				else
				{
					ppNode->_right = subR;
				}
				subR->_parent = ppNode;
			}
			//修改平衡因子
			parent->_bf = subR->_bf = 0;
		}


		void RotateLR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			int bf = subLR->_bf;//记录调整节点之前，subLR的平衡因子，因为subLR最后是新根
			//开始调整
			RotateL(parent->_left);
			RotateR(parent);

			//修改平衡因子
			if (bf == -1)//说明是在左子树上新增节点，即图中的b子树
			{
				parent->_bf = 1;
				subL->_bf = 0;
				subLR->_bf = 0;
			}
			else if (bf == 1)//说明是在右子树c上新增节点
			{
				parent->_bf = 0;
				subL->_bf = -1;
				subLR->_bf = 0;
			}
			else if (bf == 0)//说明subLR自己就是新增的节点
			{
				parent->_bf = 0;
				subL->_bf = 0;
				subLR->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}

		void RotateRL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			int bf = subRL->_bf;//记录调整节点之前，subRL的平衡因子，因为subRL最后是新根

			RotateR(parent->_right);
			RotateL(parent);

			if (bf == 1) //在右子树上新增节点
			{
				parent->_bf = -1;
				subR->_bf = 0;
				subRL->_bf = 0;
			}
			else if (bf == -1) //在左子树上新增节点
			{
				parent->_bf = 0;
				subR->_bf = 1;
				subRL->_bf = 0;
			}
			else if (bf == 0) //说明subRL本身就是那个新增的节点
			{
				parent->_bf = 0;
				subR->_bf = 0;
				subRL->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}

		void Inorder()
		{
			_Inorder(_root);
		}

		void _Inorder(Node* root)
		{
			if (root == nullptr)
				return;

			_Inorder(root->_left);
			cout << root->_kv.first << ": " << root->_kv.second << endl;
			_Inorder(root->_right);
		}

		int Height(Node* root)
		{
			if (root == nullptr)
			{
				return 0;
			}
			//先计算左子树的高度
			int ln = Height(root->_left);
			//然后计算右子树的高度
			int rn = Height(root->_right);

			return ln > rn ? ln + 1 : rn + 1;
		}

		bool IsBalance()
		{
			return IsBalance(_root);
		}

		bool IsBalance(Node* root)
		{
			if (root == nullptr)
				return true;

			//计算当前节点root的平衡因子
			int leftHeight = Height(root->_left);
			int rightHeight = Height(root->_right);

			//如果不同，那就将当前节点的值打印出来，并提升异常
			if (rightHeight - leftHeight != root->_bf)
			{
				cout << root->_kv.first << "平衡因子异常" << endl;
				return false;
			}
			//通过递归，验证每一个节点的平衡因子是否符合
			return abs(rightHeight - leftHeight) < 2
				&& IsBalance(root->_left)
				&& IsBalance(root->_right);
		}

	private:
		Node* _root = nullptr;
	};




